/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef __STD_ALGORITHM_H_VERSION_SSTD__
#define __STD_ALGORITHM_H_VERSION_SSTD__

#include "buffer.hpp"
#include "numeric.hpp"
#include "sort.hpp"

SSTL_BEGIN
// FUNCTION adjacent_difference {
template<typename InIter, typename OutIter>
inline OutIter adjacent_difference(InIter first, InIter last, OutIter dest)
{
	if (first == last) return dest;
	typename iterator_traits<InIter>::type value = *first;
	*dest = value;
	for (++dest; ++first != last; ++dest)
	{
		typename iterator_traits<InIter>::type temp = *first;
		*dest = temp - value;
		value = temp;
	}
	return dest;
}
template<typename InIter, typename OutIter, typename Minus>
inline OutIter adjacent_difference(InIter first, InIter last,
	OutIter dest, Minus fun)
{
	if (first == last) return dest;
	typename iterator_traits<InIter>::type value = *first;
	*dest = value;
	for (++dest; ++first != last; ++dest)
	{
		typename iterator_traits<InIter>::type temp = *first;
		*dest = fun(temp, value);
		value = temp;
	}
	return dest;
}
// FUNCTION adjacent_difference }
// FUNCTION adjacent_find {
template<typename InIter>
inline InIter adjacent_find(InIter first, InIter last)
{
	return adjacent_find(first, last,
		SSTD::equal_to<iterator_traits<InIter>::type>());
}
template<typename InIter, typename Equal>
inline InIter adjacent_find(InIter first, InIter last, Equal fun)
{
	if (first == last) return last;
	InIter temp = first;
	while (++first != last)
	{
		if (fun(*temp, *first)) return temp;
		temp = first;
	}
	return last;
}
// FUNCTION adjacent_find }
// FUNCTION binary_search {
template<typename RanIter, typename Value>
inline bool binary_search(RanIter const& first, RanIter const& last,
	Value const& value)
{
	RanIter result = lower_bound(first, last, value);
	return (result != last && !(value < *result));
}
template<typename RanIter, typename Value, typename Less>
inline bool binary_search(RanIter const& first, RanIter const& last,
	Value const& value, Less fun)
{
	RanIter result = lower_bound(first, last, value, fun);
	return (result != last && !fun(value, *result));
}
// FUNCTION binary_search }
// FUNCTION lower_bound {
template<typename RanIter, typename Value, typename Less>
inline RanIter lower_bound(RanIter first, RanIter last, Value const& value, Less fun)
{
	size_t count = SSTD::distance(first, last);
	while (count)
	{
		size_t mid_pos = count / 2;
		RanIter middle = first + mid_pos;
		if (fun(*middle, value)) first = ++middle, count -= mid_pos + 1;
		else last = middle, count = mid_pos;
	}
	return first;
}
template<typename RanIter, typename Value>
inline RanIter lower_bound(RanIter first, RanIter last, Value const& value)
{
	return lower_bound(first, last, value,
		SSTD::less2<iterator_traits<RanIter>::type, Value>());
}
// FUNCTION lower_bound }
// FUNCTION upper_bound {
template<typename RanIter, typename Value, typename Less>
inline RanIter upper_bound(RanIter first, RanIter last, Value const& value, Less fun)
{
	size_t count = SSTD::distance(first, last);
	while (count)
	{
		size_t mid_pos = count / 2;
		RanIter middle = first + mid_pos;
		if (fun(value, *middle)) last = middle, count = mid_pos;
		else first = ++middle, count -= mid_pos + 1;
	}
	return first;
}
template<typename RanIter, typename Value>
inline RanIter upper_bound(RanIter first, RanIter last, Value const& value)
{
	return upper_bound(first, last, value,
		SSTD::less2<iterator_traits<RanIter>::type, Value>());
}
// FUNCTION upper_bound }
// FUNCTION copy, copy_n, copy_backward {
template<class InIter, class OutIter>
inline OutIter copy(InIter const& first, InIter const& last, OutIter const& dest)
{
	return SSTD::_memory_helper_<iterator_traits<InIter>::value_type>
		::copy(first, last, dest);
}
template<class InIter, class OutIter>
inline OutIter copy_n(InIter const& first, size_t num, OutIter const& dest)
{
	return SSTD::_memory_helper_<iterator_traits<InIter>::value_type>
		::copy_n(first, num, dest);
}
template<class InIter, class OutIter>
inline OutIter copy_backward(InIter const& first, InIter const& last,
	OutIter const& dest_last)
{
	return SSTD::_memory_helper_<iterator_traits<InIter>::value_type>
		::copy_backward(first, last, dest_last);
}
// FUNCTION copy, copy_n, copy_backward }
// FUNCTION count, count_if {
template<class InIter, class Value>
inline size_t count(InIter first, InIter last, Value const& value)
{
	size_t num = 0;
	for (; first != last; ++first)
	{
		if (value == *first) ++num;
	}
	return num;
}
template<class InIter, class Bool>
inline size_t count_if(InIter first, InIter last, Bool fun)
{
	size_t num = 0;
	for (; first != last; ++first)
	{
		if (fun(*first)) ++num;
	}
	return num;
}
// FUNCTION count, count_if }
// FUNCTION equal_range {
template<typename RanIter, typename Value>
static SSTD::pair<RanIter, RanIter>
equal_range(RanIter first, RanIter last, Value const& value)
{
	return equal_range(first, last, value,
		SSTD::less2<iterator_traits<RanIter>::type, Value>());
}
template<typename RanIter, typename Value, typename Less>
static SSTD::pair<RanIter, RanIter>
equal_range(RanIter first, RanIter last, Value const& value, Less fun)
{
	size_t count = SSTD::distance(first, last);
	while (count)
	{
		size_t mid_pos = count / 2;
		RanIter middle = first + mid_pos;
		if (fun(*middle, value)) first = ++middle, count -= mid_pos + 1;
		else if (fun(value, *middle)) last = middle, count = mid_pos;
		else
		{
			return SSTD::make_pair(lower_bound(first, middle, value, fun),
				upper_bound(middle, last, value, fun));
		}
	}
	return SSTD::make_pair(first, first);
}
// FUNCTION equal_range }
// FUNCTION equal {
template<class InIterL, class InIterR>
inline bool equal(InIterL first0, InIterL last0, InIterR first)
{
	for (; first0 != last0 && *first0 == *first; ++first0, ++first);
	return first0 == last0;
}
template<class InIterL, class InIterR, class Equal>
inline bool equal(InIterL first0, InIterL last0, InIterR first, Equal fun)
{
	for (; first0 != last0 && fun(*first0, *first); ++first0, ++first);
	return first0 == last0;
}
// FUNCTION equal }
// FUNCTION fill, fill_n {
template<typename OutIter, typename Value>
void fill(OutIter first, OutIter last, Value const& value)
{
	for (; first != last; ++first) *first = value;
}
template<typename OutIter, typename Value>
void fill_n(OutIter first, size_t num, Value const& value)
{
	for (; num--; ++first) *first = value;
}
// FUNCTION fill, fill_n }
// FUNCTION find, find_end, find_if, find_first_of {
template<typename InIter, typename Value>
inline InIter find(InIter first, InIter last, Value const& value)
{
	for (; first != last && *first != value; ++first);
	return first;
}
template<typename InIterSrc, typename InIterDest>
inline InIterSrc find_end(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last)
{
	return search_end(first0, last0, first, last);
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc find_end(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last, Equal fun)
{
	return search_end(first0, last0, first, last, fun);
}
template<typename InIter, typename Func1>
inline InIter find_if(InIter first, InIter last, Func1 fun)
{
	for (; first != last && !fun(*first); ++first);
	return first;
}
template<typename InIterSrc, typename InIterDest>
inline InIterSrc find_first_of(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last)
{
	for (; first0 != last0; ++first0)
	{
		InIterDest head = first;
		typedef typename SSTD::iterator_traits<InIterSrc>::type type;
		type& value = *first0;
		for (; head != last; ++head)
		{
			if (value == *head) return first0;
		}
	}
	return last0;
}
// FUNCTION find, find_end, find_if, find_first_of }
// FUNCTION foreach {
template<typename InIter, typename Func1>
inline Func1 foreach(InIter first, InIter last, Func1 fun)
{
	for (; first != last; ++first) fun(*first);
	return fun;
}
// FUNCTION foreach }
// FUNCTION generate, generate_n {
template<typename OutIter, typename Func0>
inline void generate(OutIter first, OutIter last, Func0 fun)
{
	for (; first != last; ++first) *first = fun();
}
template<typename OutIter, typename Func0>
inline OutIter generate_n(OutIter first, size_t num, Func0 fun)
{
	for (; num--; ++first) *first = fun();
	return first;
}
// FUNCTION generate, generate_n }
// FUNCTION includes {
template<typename InIterL, typename InIterR>
inline bool includes(InIterL first0, InIterL last0,
	InIterR first, InIterR last)
{
	for (; first != last; ++first)
	{
		for (; first0 != last0 && *first0 < *first; ++first0);
		if (first0 == last0 || *first < *first0) return false;
	}
	return true;
}
template<typename InIterL, typename InIterR, typename Less>
inline bool includes(InIterL first0, InIterL last0,
	InIterR first, InIterR last, Less fun)
{
	for (; first != last; ++first)
	{
		for (; first0 != last0 && less(*first0, *first); ++first0);
		if (first0 == last0 || less(*first, *first0)) return false;
	}
	return true;
}
// FUNCTION includes }
// FUNCTION is_sorted {
template<typename InIter>
inline bool is_sorted(InIter first, InIter last)
{
	if (first == last) return true;
	InIter temp = first;
	while (++first != last)
	{
		if (*first < *temp) return false;
		temp = first;
	}
	return true;
}
template<typename InIter, typename Less>
inline bool is_sorted(InIter first, InIter last, Less fun)
{
	if (first == last) return true;
	InIter temp = first;
	while (++first != last)
	{
		if (fun(*first, *temp)) return false;
		temp = first;
	}
	return true;
}
// FUNCTION is_sorted }
// FUNCTION iter_swap {
template<typename AddressL, typename AddressR>
inline void iter_swap(AddressL left, AddressR right)
{
	SSTD::swap(*left, *right);
}
// FUNCTION iter_swap }
// FUNCTION lexicographical_compare lexicographical_compare_3way{
template<typename InIterL, typename InIterR>
inline bool lexicographical_compare(InIterL first0, InIterL last0,
	InIterR first, InIterR last)
{
	return SSTD::lexicographical_compare(first0, last0, first, last,
		SSTD::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename Less>
inline bool lexicographical_compare(InIterL first0, InIterL last0,
	InIterR first, InIterR last, Less less)
{
	for (; first0 != last0 && first != last; ++first0, ++first)
	{
		if (less(*first0, *first)) return true;
		if (less(*first, *first0)) return false;
	}
	return !(first0 != last0 || first == last);
}
template<typename InIterL, typename InIterR>
inline int lexicographical_compare_3way(InIterL first0, InIterL last0,
	InIterR first, InIterR last)
{
	return SSTD::lexicographical_compare_3way(first0, last0, first, last,
		SSTD::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename Less>
inline int lexicographical_compare_3way(InIterL first0, InIterL last0,
	InIterR first, InIterR last, Less less)
{
	for (; first0 != last0 && first != last; ++first0, ++first)
	{
		if (less(*first0, *first)) return -1;
		if (less(*first, *first0)) return 1;
	}
	return (first0 != last0) ? 1 : ((first != last) ? -1 : 0);
}
// FUNCTION lexicographical_compare lexicographical_compare_3way}
// FUNCTION smaller, min_element, bigger, max_element {
// --- some c header has defined the macro "min" and "max".
// --- use "smaller" and "bigger" as replacements.
template<typename Type>
inline Type& smaller(Type& first, Type& second)
{
	if (second < first) return second;
	return first;
}
template<typename Type>
inline Type& bigger(Type& first, Type& second)
{
	if (first < second) return second;
	return first;
}
template<typename Type>
inline const Type& smaller(const Type& first, const Type& second)
{
	if (second < first) return second;
	return first;
}
template<typename Type>
inline const Type& bigger(const Type& first, const Type& second)
{
	if (first < second) return second;
	return first;
}
template<typename Type, typename Less>
inline Type& smaller(Type& first, Type& second, Less less)
{
	if (less(second, first)) return second;
	return first;
}
template<typename Type, typename Less>
inline Type& bigger(Type& first, Type& second, Less less)
{
	if (less(first, second)) return second;
	return first;
}
template<typename Type, typename Less>
inline const Type& smaller(const Type& first, const Type& second, Less less)
{
	if (less(second, first)) return second;
	return first;
}
template<typename Type, typename Less>
inline const Type& bigger(const Type& first, const Type& second, Less less)
{
	if (less(first, second)) return second;
	return first;
}
template<typename InIter>
inline InIter min_element(InIter first, InIter last)
{
	if (first == last) return last;
	InIter result = first;
	while (++first != last) if (*first < *result) result = first;
	return result;
}
template<typename InIter>
inline InIter max_element(InIter first, InIter last)
{
	if (first == last) return last;
	InIter result = first;
	while (++first != last) if (*result < *first) result = first;
	return result;
}
template<typename InIter, typename Less>
inline InIter min_element(InIter first, InIter last, Less less)
{
	if (first == last) return last;
	InIter result = first;
	while (++first != last) if (less(*first, *result)) result = first;
	return result;
}
template<typename InIter, typename Less>
inline InIter max_element(InIter first, InIter last, Less less)
{
	if (first == last) return last;
	InIter result = first;
	while (++first != last) if (less(*result, *first)) result = first;
	return result;
}
// FUNCTION smaller, min_element, bigger, max_element }
// FUNCTION mismatch {
template<typename InIterL, typename InIterR>
inline SSTD::pair<InIterL, InIterR> mismatch(InIterL first0, InIterL last0,
	InIterR first)
{
	return mismatch(first0, last0, first,
		SSTD::equal_to2<iterator_traits<InIterL>::type, iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename Equal>
inline SSTD::pair<InIterL, InIterR> mismatch(InIterL first0, InIterL last0,
	InIterR first, Equal fun)
{
	for (; first0 != last0; ++first0, ++first)
	{
		if (!fun(*first0, *first)) break;
	}
	return SSTD::pair<InIterL, InIterR>(first0, first);
}
// FUNCTION mismatch }
// FUNCTION next_permutation, prev_permutation {
template<typename BidIter>
inline bool next_permutation(BidIter first, BidIter last)
{
	return SSTD::next_permutation(first, last,
		SSTD::less<typename iterator_traits<BidIter>::type>());
}
template<typename BidIter, typename Less>
inline bool next_permutation(BidIter first, BidIter last, Less fun)
{
	if (first == last) return false;
	BidIter next = last; --next;
	if (first == next) return false;
	BidIter prev = next;
	for (; first != next;)
	{
		if (fun(*--prev, *next))
		{
			BidIter dest = last; while (!fun(*prev, *--dest));
			SSTD::iter_swap(prev, dest);
			SSTD::reverse(next, last);
			return true;
		}
		next = prev;
	}
	SSTD::reverse(first, last);
	return false;
}
template<typename BidIter>
inline bool prev_permutation(BidIter first, BidIter last)
{
	return SSTD::prev_permutation(first, last,
		SSTD::less<typename iterator_traits<BidIter>::type>());
}
template<typename BidIter, typename Less>
inline bool prev_permutation(BidIter first, BidIter last, Less fun)
{
	if (first == last) return false;
	BidIter next = last; --next;
	if (first == next) return false;
	BidIter prev = next;
	for (; first != next;)
	{
		if (fun(*next, *--prev))
		{
			BidIter dest = last; while (!fun(*--dest, *prev));
			SSTD::iter_swap(prev, dest);
			SSTD::reverse(next, last);
			return true;
		}
		next = prev;
	}
	SSTD::reverse(first, last);
	return false;
}
// FUNCTION next_permutation, prev_.. }
// FUNCTION random_sample {
template<typename RanIter, typename RanIterDest>
inline RanIterDest random_sample(RanIter first0, RanIter last0,
	RanIterDest d_first, RanIterDest d_last)
{
	ASSERT(false);
	do some thing here;
	return d_last;
}
template<typename RanIter, typename RanIterDest>
inline RanIterDest random_sample_n(RanIter first0, RanIter last0,
	RanIterDest d_first, size_t num)
{
	ASSERT(false);
	do some thing here;
	return d_first + num;
}
// FUNCTION random_sample }
// FUNCTION random_shuffle {
template<typename RanIter>
inline void random_shuffle(RanIter first, RanIter last)
{
	size_t num = SSTD::distance(first, last);
	if (num <= 0) return;
	for (RanIter temp = first; temp != last; ++temp)
	{
		SSTD::iter_swap(temp, first + diff_t(::rand() % num));
	}
}
template<typename RanIter, typename Random>
inline void random_shuffle(RanIter first, RanIter last, Random rand)
{
	size_t num = SSTD::distance(first, last);
	if (num <= 0) return;
	for (RanIter temp = first; temp != last; ++temp)
	{
		SSTD::iter_swap(temp, first + diff_t(rand() % num));
	}
}
// FUNCTION random_shuffle }
// FUNCTION remove, remove_if, remove_copy, remove_copy_if {
template<typename FwdIter, typename Value>
inline FwdIter remove(FwdIter first, FwdIter last, Value const& value)
{
	while (first != last && !(*first == value)) ++first;
	if (first == last) return last;
	FwdIter dest = first;
	while (++first != last)
	{
		if (*first == value) continue;
		*dest++ = *first;
	}
	return dest;
}
template<typename FwdIter, typename Bool>
inline FwdIter remove_if(FwdIter first, FwdIter last, Bool fun)
{
	while (first != last && !fun(*first)) ++first;
	if (first == last) return last;
	FwdIter dest = first;
	while (++first != last)
	{
		if (fun(*first)) continue;
		*dest++ = *first;
	}
	return dest;
}
template<typename FwdIter, typename FwdIterDest, typename Value>
inline FwdIterDest remove_copy(FwdIter first, FwdIter last, FwdIterDest result, Value const& value)
{
	for (; first != last; ++first)
	{
		if (*first == value) continue;
		*result++ = *first;
	}
	return result;
}
template<typename FwdIter, typename FwdIterDest, typename Bool>
inline FwdIterDest remove_copy_if(FwdIter first, FwdIter last, FwdIterDest result, Bool fun)
{
	for (; first != last; ++first)
	{
		if (fun(*first)) continue;
		*result++ = *first;
	}
	return result;
}
// FUNCTION remove, remove_if, remove_copy, remove_copy_if }
// FUNCTION replace, replace_if, replace_copy, replace_copy_if {
template<typename FwdIter, typename Value>
inline void replace(FwdIter first, FwdIter last,
	Value const& old_value, Value const& new_value)
{
	for (; first != last; ++first) if (*first == old_value) *first = new_value;
}
template<typename FwdIter, typename Bool, typename Value>
inline void replace_if(FwdIter first, FwdIter last, Bool fun, Value const& new_value)
{
	for (; first != last; ++first) if (fun(*first)) *first = new_value;
}
template<typename FwdIter, typename FwdIterDest, typename Value>
inline void replace_copy(FwdIter first, FwdIter last, FwdIterDest result,
	Value const& old_value, Value const& new_value)
{
	for (; first != last; ++first, ++result)
	{
		if (*first == old_value) *result = new_value;
		else *result = *first;
	}
}
template<typename FwdIter, typename FwdIterDest, typename Bool, typename Value>
inline void replace_copy_if(FwdIter first, FwdIter last, FwdIterDest result,
	Bool fun, Value const& new_value)
{
	for (; first != last; ++first, ++result)
	{
		if (fun(*first)) *result = new_value;
		else *result = *first;
	}
}
// FUNCTION replace, replace_if, replace_copy, replace_copy_if }
// FUNCTION reverse, reverse_copy {
template<typename BidIter>
inline void reverse(BidIter first, BidIter last)//, SSTD::bidirectional_iterator_tag)
{
	for (; first != last && first != --last; ++first)
	{
		SSTD::iter_swap(first, last);
	}
}
template<typename BidIter, typename FwdIter>
inline FwdIter reverse_copy(BidIter first, BidIter last, FwdIter result)
{
	while (first != last) *result++ = *--last;
	return result;
}
// FUNCTION reverse, reverse_copy }
// FUNCTION rotate_copy {
template<typename FwdIter>
inline FwdIter rotate(FwdIter first, FwdIter mid, FwdIter last)
{
	if (first == mid) return last;
	if (mid == last) return first;
	typedef iterator_traits<FwdIter>::type type;
	typedef SSTD::_memory_helper_<type> _helper;
	size_t num1 = SSTD::distance(first, mid);
	size_t num2 = SSTD::distance(mid, last);
	if (num1 <= num2)
	{
		SSTD::raw_buffer<type> buf(num1);
		_helper::raw_copy_n(first, num1, buf.begin());
		first = copy_n(mid, num2, first);
		copy_n(buf.begin(), buf.size(), first);
		_helper::destroy_n(buf.begin(), num1);
	}
	else
	{
		SSTD::raw_buffer<type> buf(num1);
		_helper::raw_copy_n(first, num2, buf.begin());
		first = SSTD::copy_n(mid, num2, first);
		SSTD::copy_backward(first, mid, last);
		SSTD::copy_n(buf.begin(), buf.size(), first);
		_helper::destroy_n(buf.begin(), num2);
	}
	return first;
}
template<typename InIter, typename OutIter>
inline OutIter rotate_copy(InIter first, InIter mid, InIter last, OutIter dest)
{
	dest = SSTD::copy(mid, last, dest);
	SSTD::copy(first, mid, dest);
	return dest;
}
// FUNCTION rotate_copy }
// FUNCTION search, search_n {
template<typename InIterSrc, typename InIterDest>
inline InIterSrc search(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last)
{
	return SSTD::search(first0, last0, first, last,
		SSTD::equal_to2<iterator_traits<InIterSrc>::type,
		iterator_traits<InIterDest>::type>());
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc search(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last, Equal fun)
{
	size_t obj_num = SSTD::distance(first, last);
	if (obj_num == 0) return first0;
	size_t src_num = SSTD::distance(first0, last0);
	for (; src_num >= obj_num; ++first0, --src_num)
	{
		InIterSrc src = first0;
		InIterDest head = first;
		size_t num = obj_num;
		for (; num && fun(*src, *head); ++head, ++src, --num);
		if (!num) return first0;
	}
	return last0;
}
template<typename InIterSrc, typename InIterDest>
inline InIterSrc search_end(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last)
{
	return SSTD::search_end(first0, last0, first, last,
		SSTD::equal_to2<iterator_traits<InIterSrc>::type,
		iterator_traits<InIterDest>::type>());
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc search_end(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last, Equal fun)
{
	return SSTD::_search_end_(first0, last0, first, last, fun,
		SSTD::iterator_category(first0), SSTD::iterator_category(first));
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc _search_end_(InIterSrc first0, InIterSrc last0,
	InIterDest first, InIterDest last, Equal fun,
	SSTD::input_iterator_tag*,
	SSTD::input_iterator_tag*)
{
	size_t obj_num = SSTD::distance(first, last);
	if (obj_num == 0) return first0;
	InIterSrc result = last0;
	size_t src_num = SSTD::distance(first0, last0);
	for (; src_num >= obj_num; ++first0, --src_num)
	{
		InIterSrc src = first0;
		InIterDest head = first;
		size_t num = obj_num;
		for (; num && fun(*src, *head); ++head, ++src, --num);
		if (!num) result = first0;
	}
	return result;
}
template<typename BidIterSrc, typename BidIterDest, typename Equal>
inline BidIterSrc _search_end_(BidIterSrc first0, BidIterSrc last0,
	BidIterDest first, BidIterDest last, Equal fun,
	SSTD::bidirectional_iterator_tag*,
	SSTD::bidirectional_iterator_tag*)
{
	size_t obj_num = SSTD::distance(first, last);
	if (obj_num == 0) return first0;
	size_t src_num = SSTD::distance(first0, last0);
	for (first0 = last0; src_num >= obj_num; --first0, --src_num)
	{
		BidIterSrc src = first0;
		size_t num = obj_num;
		for (first = last; num && fun(*--src, *--first); --num);
		if (!num) return src;
	}
	return last0;
}
template<typename InIterSrc, typename Value>
inline InIterSrc search_n(InIterSrc first0, InIterSrc last0,
	size_t num, Value const& value)
{
	return search_n(first0, last0, num, value,
		SSTD::equal_to2<iterator_traits<InIterSrc>::type, Value>());
}
template<typename InIterSrc, typename Value, typename Equal>
inline InIterSrc search_n(InIterSrc first0, InIterSrc last0,
	size_t num, Value const& value, Equal fun)
{
	return SSTD::_search_n_(first0, last0, num, value, fun,
		SSTD::iterator_category(first0));
}
template<typename InIterSrc, typename Value, typename Equal>
inline InIterSrc _search_n_(InIterSrc first0, InIterSrc last0,
	size_t num, Value const& value, Equal& fun,
	SSTD::random_access_iterator_tag*)
{
	if (num == 0) return first0;
	size_t src_num = SSTD::distance(first0, last0);
	size_t off = 0;
	while (src_num >= num)
	{
		InIterSrc tail = first0 + num;
		size_t off2 = 0;
		while (fun(*--tail, value))
		{
			if (off + (++off2) == num) return first0;
		}
		first0 = ++tail;
		off = off2;
		src_num -= num - off2;
	}
	return last0;
}
template<typename InIterSrc, typename Value, typename Equal>
inline InIterSrc _search_n_(InIterSrc first0, InIterSrc last0,
	size_t num, Value const& value, Equal& fun,
	SSTD::input_iterator_tag*)
{
	if (num == 0) return first0;
	while (first0 != last0)
	{
		if (fun(*first0, value))
		{
			size_t count = num;
			InIterSrc result = first0;
			do {
				if (--count == 0) return result;
			} while (first0 != last0 && fun(*++first0, value));
		}
		else ++first0;
	}
	return last0;
}
// FUNCTION search, search_n }
// FUNCTION set_difference, set_symmetric_difference, set_intersection, set_union {
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_difference(InIterL first0, InIterL last0,
	InIterR first, InIterR last, OutIter result)
{
	return SSTD::set_difference(first0, last0, first, last, result,
		SSTD::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_difference(InIterL first0, InIterL last0,
	InIterR first, InIterR last,
	OutIter result, Less fun)
{
	while (first0 != last0 && first != last)
	{
		if (fun(*first0, *first)) *result = *first0, ++result, ++first0;
		else if (fun(*first, *first0)) ++first;
		else ++first0, ++first;
	}
	return SSTD::copy(first0, last0, result);
}
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_symmetric_difference(InIterL first0, InIterL last0,
	InIterR first, InIterR last, OutIter result)
{
	return SSTD::set_symmetric_difference(first0, last0, first, last, result,
		SSTD::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_symmetric_difference(InIterL first0, InIterL last0,
	InIterR first, InIterR last,
	OutIter result, Less fun)
{
	while (first0 != last0 && first != last)
	{
		if (fun(*first0, *first)) *result = *first0, ++result, ++first0;
		else if (fun(*first, *first0)) *result = *first, ++result, ++first;
		else ++first0, ++first;
	}
	result = SSTD::copy(first0, last0, result);
	return SSTD::copy(first, last, result);
}
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_intersection(InIterL first0, InIterL last0,
	InIterR first, InIterR last, OutIter result)
{
	return SSTD::set_intersection(first0, last0, first, last, result,
		SSTD::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_intersection(InIterL first0, InIterL last0,
	InIterR first, InIterR last,
	OutIter result, Less fun)
{
	while (first0 != last0 && first != last)
	{
		if (fun(*first0, *first)) ++first0;
		else if (fun(*first, *first0)) ++first;
		else *result = *first, ++first0, ++first, ++result;
	}
	return result;
}
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_union(InIterL first0, InIterL last0,
	InIterR first, InIterR last, OutIter result)
{
	return SSTD::set_union(first0, last0, first, last, result,
		SSTD::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_union(InIterL first0, InIterL last0,
	InIterR first, InIterR last,
	OutIter result, Less fun)
{
	while (first0 != last0 && first != last)
	{
		if (fun(*first0, *first)) *result = *first0, ++first0, ++result;
		else if (fun(*first, *first0)) *result = *first, ++first, ++result;
		else *result = *first, ++first0, ++first, ++result;
	}
	result = SSTD::copy(first0, last0, result);
	return SSTD::copy(first, last, result);
}
// FUNCTION set_difference, set_symmetric_difference, set_intersection, set_union }
// FUNCTION swap_ranges {
template<typename FwdIterL, typename FwdIterR>
inline FwdIterR swap_ranges(FwdIterL first0, FwdIterL last0, FwdIterR first)
{
	for (; first0 != last0; ++first0, ++first) SSTD::iter_swap(first0, first);
	return first;
}
// FUNCTION swap_ranges }
// FUNCTION transform {
template<typename InIter, typename OutIter, typename Func1>
inline OutIter transform(InIter first, InIter last, OutIter result, Func1 fun)
{
	for (; first != last; ++first, ++result) *result = fun(*first);
	return result;
}
template<typename InIterL, typename InIterR, typename OutIter, typename Func1>
inline OutIter transform(InIterL first0, InIterL last0,
	InIterR first, OutIter result, Func1 fun)
{
	for (; first0 != last0; ++first, +first0, ++result)
		*result = fun(*first0, *first);
	return result;
}
// FUNCTION transform }
// FUNCTION unique, unique_copy {
template<typename FwdIter, typename Equal>
inline FwdIter unique(FwdIter first, FwdIter last, Equal fun)
{
	if (first == last) return last;
	FwdIter temp = first;
	while (++first != last && !fun(*first, *temp)) temp = first;
	if (first == last) return last;
	while (++first != last) if (!fun(*first, *temp)) *++temp = *first;
	return ++temp;
}
template<typename FwdIter>
inline FwdIter unique(FwdIter first, FwdIter last)
{
	return unique(first, last,
		SSTD::equal_to<SSTD::iterator_traits<FwdIter>::type>());
}
template<typename FwdIter, typename OutIter, typename Equal>
inline FwdIter unique_copy(FwdIter first, FwdIter last,
	OutIter result, Equal fun)
{
	if (first == last) return result;
	*result = *first;
	while (++first != last) if (!fun(*first, *result)) *++result = *first;
	return ++result;
}
template<typename FwdIter, typename OutIter>
inline FwdIter unique_copy(FwdIter first, FwdIter last, OutIter result)
{
	return unique_copy(first, last, result,
		SSTD::equal_to<SSTD::iterator_traits<FwdIter>::type>());
}
// FUNCTION unique, unique_copy }
SSTL_END

#endif // __STD_ALGORITHM_H_VERSION_SSTD__
/********************* resume **********************

// numeric.
SSTD::accumulate
SSTD::adjacent_difference
SSTD::inner_product
SSTD::iota
SSTD::partial_sum
SSTD::power

// find.
SSTD::adjacent_find
SSTD::count SSTD::count_if
SSTD::find SSTD::find_if SSTD::find_first_of SSTD::find_end
SSTD::mismatch
SSTD::search (SSTD::search_end) SSTD::search_n

// compare.
SSTD::equal
SSTD::lexicographical_compare
SSTD::lexicographical_compare_3way
SSTD::smaller SSTD::min_element
SSTD::bigger SSTD::max_element

// move data.
SSTD::copy SSTD::copy_n SSTD::copy_backward
SSTD::fill SSTD::fill_n
SSTD::iter_swap
SSTD::next_permutation SSTD::prev_permutation
SSTD::random_shuffle SSTD::random_sample(X) SSTD::random_sample_n(X)
SSTD::remove SSTD::remove_copy SSTD::remove_if SSTD::remove_copy_if
SSTD::replace SSTD::replace_copy SSTD::remove_if SSTD::replace_copy_if
SSTD::swap SSTD::swap_ranges
SSTD::unique SSTD::unique_copy

// set.
SSTD::includes
SSTD::set_difference
SSTD::set_intersection
SSTD::set_symmetric_difference
SSTD::set_union

// apply function.
SSTD::foreach
SSTD::generate SSTD::generate_n
SSTD::transform

// sort.
SSTD::is_heap
SSTD::push_heap SSTD::pop_heap
SSTD::make_heap SSTD::sort_heap
SSTD::nth_element
SSTD::partial_sort SSTD::partial_sort_copy
SSTD::partition SSTD::stable_partition
SSTD::sort SSTD::stable_sort
SSTD::merge SSTD::inplace_merge

// binary
SSTD::binary_search
SSTD::equal_range
SSTD::lower_bound
SSTD::upper_bound

********************* resume **********************/
